1. Technical Field
The invention relates to a computer system for accessing a stored data base comprising a number of blocks, each of said blocks containing a plurality of data files and a directory with the access keys of the files stored in each of the respective blocks, and comprising means for effecting a sorted ordering of the data files such that the access keys in each block have a predetermined relation.
2. Description of the Prior Art
In large computer systems having a processor, memory, and a storage device, a data base can be stored in the storage device as a plurality of data files arranged in plurality of blocks, wherein each data file is uniquely identified using an access key, and each block contains a directory of the access keys for the files in the respective block. When a data file is accessed (when updating or querying the data base), the access key is used to identify the data file that is to be accessed (the requested data file). When items such as data files in storage on a computer disk have to be sequentially searched (accessed and read) to locate a key, it would be impractical, and the performance would be low. In fact in average one-half of all items would have to be read in order to find the desired item. That would involve a relatively large number of disk read operations. In the past, efforts have been made to reduce this number of disk read operations.
An example of a system of the above mentioned type is described in the Canadian Patent 964.373. In this prior art system an appropriate file organization is provided, such that a data file can be read from a disk master file given the file name, by performing one seek and one read operation. The process of locating and reading a data file entails the hash coding of a file name to yield a block address, the moving of the read head to the disk area having the block address and the reading of the directory and the remainder of the block to read out the data file. During the reading of the directory, the data file names are compared in real time, as they are read from the disk, with the name of the desired data file. When a name match occurs, the address of the data file in the block and the address of the succeeding file in the same block are read and stored. As the disk rotates the desired data file address just read is constantly compared with the active disk address. When a match occurs the file has been located and is read out. The reading is terminated at the address of the beginning of the next file. If the file name is not found in the directory of the block indicated by the hash coding of the file's name, then the file is not present therein.
Although the access time to a specific data file is considerably reduced if the above described prior art system is applied, another disadvantage is introduced instead; i.e., the necessity to use a hash coding of all the file names. Through this hash coding the address of the block in which a specific file is stored can be retrieved. However, because of the hash coding this prior art method is not applicable to existing systems without changing the layout and the structure of at least the file names.
An object of the invention is now to provide a data base access system which can be applied to any arbitrary data base search mechanism without any change in the layout or structure of the search data and yet results into an appreciable reduction of the number of disk read operations and therewith of the file access time.